package com.topInterview;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * @Author: huangzhigao
 * @Date: 2022/2/19 15:49
 */
public class Leecode22_generatorParenthness {
    public List<String> generateParenthesis(int n) {
        char[] chars = new char[n << 1];
        List<String> res = new ArrayList<>();
        process(chars, 0, 0, n, res);
        return res;
    }


    /**
     * @param path
     * @param index          index当前所在的位置
     * @param leftMinusRight 左括号 - 右括号的数
     * @param leftRest       当前还可以填做左括号的个数
     * @param ans            结果
     */
    public void process(char[] path, int index, int leftMinusRight, int leftRest, List<String> ans) {
        if (index == path.length) {
            ans.add(String.valueOf(path));
        } else {
            if (leftRest > 0) {
                path[index] = '(';
                process(path, index+1, leftMinusRight + 1, leftRest - 1, ans);
            }
            if (leftMinusRight > 0) {
                path[index] = ')';
                process(path, index+1, leftMinusRight - 1, leftRest, ans);
            }
        }
    }

    public static void main(String[] args) {
        Leecode22_generatorParenthness s = new Leecode22_generatorParenthness();
        s.generateParenthesis(3);
    }
}
